1. Field of the Invention
The present invention relates generally to the field of querying a database of images and particularly to providing an interface for organizing the results of queries applied to a database of images.
2. Description of the Related Art
Search engines are some of the most popular and widely accessed sites on the World Wide Web (WWW) because they allow a user to find information of interest. These engines gather textual information about resources on the Web and build up indices. The indices allow for the retrieval of documents containing user specified keywords. Another method of searching for information on the Web utilizes subject-based directories, which provide a useful browsable organization of information.
However, with the explosive growth of information that is available on the WWW, most queries applied to the search engines result in a large number of retrieved documents. This leads to a key limitation suffered by most of the popular search engines available today. More specifically, most search engines show the results of a query as pages of scrolled lists. If a large number of documents are retrieved, scrolling through such lists to find documents of interest to the user is extremely tedious and not at all user friendly.
An image search engine, called Advanced Multimedia Oriented Retrieval Engine (AMORE), developed by the present inventors at NEC, allows the user to specify an image and find images that are visually similar to it. See Mukhetjea et al., xe2x80x9cTowards a Multimedia World-Wide Web Information Retrieval Engine,xe2x80x9d Proceedings of the Sixth International World-Wide Web Conference, pages 177-188, April, 1997. In AMORE the user can specify keywords, where all the images relevant to the keywords are retrieved. However, as more and more images are indexed, AMORE is suffering from the same problems affecting traditional text search engines. More specifically, a query presented by the user of the search engine may result in a large number of retrieved images. Many user queries result in more than 100 retrieved images. As with other search engines, AMORE shows a few of the retrieved images per page and allows the user to go to other pages of retrieved images. This is shown in FIG. 1. Obviously, this is not a very user-friendly way of displaying search results to the user of the search engine.
Various searching and clustering techniques have been proposed to attempt to make systems more user-friendly. However, most have focused on text-based mechanisms. For example, clustering has been an emerging information retrieval tool. See Salton et al., xe2x80x9cIntroduction to Modern Information Retrieval,xe2x80x9d McGraw-Hill, 1983; Van-Rijsbergen, xe2x80x9cInformation Retrieval,xe2x80x9d Butterworths, 1979. The focus has been on the use of text clustering to speed up the searching process. Instead of comparing all documents in a large collection to find the relevant documents, such efforts have focused on initially comparing only a representative cluster vector for each cluster with the search request. Thereafter, only documents from clusters which matched favorably are compared. Clustering is also useful for browsing large online collections of text as shown by a scatter/gather technique. See Cutting et al., xe2x80x9cScatter/Gather: A Cluster-based Approach to Browsing Large Document Clusters,xe2x80x9d Proceedings of the ACM SIGIR ""92 Conference on Research and Development in Information Retrieval, pages 318-329, June, 1992. Once again, this effort focuses on browsing a text collection, rather than an image collection.
In some instances, clustering has been used for searching large image databases as a pre-processing step to filter out non-interesting images. This reduces the number of images to be processed by more computer-intensive fine matching procedures. In addition, using the classification results produced by clustering, users can roughly grasp the contents of the entire image database and use this information for their interaction with the image retrieval system. Image clustering can be based on various image features such as colors, textures, shapes, etc. For example, Hirata et al., xe2x80x9cThe Concept of Media-based Navigation and Its Implementation on Hypermedia System xe2x80x9cMiyabi,xe2x80x9dxe2x80x9d NEC Research and Development, 35(4):410-420, 1994, discusses a technique that focuses on color information in an image. Color values from the image are extracted and mapped on the HLS color spaces. Based on the results, users can filter out the images before searching. On the other hand, the work described in Del Bimbo et al., xe2x80x9cShape Indexing by Structural Properties,xe2x80x9d International Conference on Human Factors in Computing Systems, page 370-377, June, 1997, clusters by shape similarity. Using multi-scale analysis, a hierarchical structure of shape is extracted. Based on this structure, searching capabilities are provided. However, this method assumes that boundary analysis correctly extracts the boundaries of objects in the image. However, this is very difficult to do for WWW images containing many objects. Similarly, image clustering using feature vectors based on moment invariant (See Flickner et al., xe2x80x9cQuery by Image and Video Content: The QBIC System,xe2x80x9d IEEE Computer, 28(9):23-31, September, 1995) or boundary features (See Mehrotra et al., xe2x80x9cSimilar-Shape Retrieval in Shape Data Management,xe2x80x9d IEEE Computer, pages 57-62, September, 1995) also assumes the correct extraction of objects (or input by a user). Therefore, it is very hard to apply these techniques to the WWW. Additionally, each of these techniques focuses on providing only a single cluster mechanism. The techniques do not address providing a user-friendly interface.
The search techniques are also being applied to the WWW. Research at Xerox Palo Alto Research Center (PARC) uses clustering to extract useful structures from the WWW. See Pirolli et al., xe2x80x9cSilk from a Sow""s Ear: Extracting Usable Structures from the Web,xe2x80x9d Proceedings of the ACM SIGCHI ""96 Conference on Human Factors in Computing Systems, pages 118-125, April, 1996; Pitkow et al, xe2x80x9cLife, Death and Lawfulness on the Electronic Frontier,xe2x80x9d Proceedings of the ACM SIGCHI ""97 Conference on Human Factors in Computing Systems, pages 383-390, March, 1997. The clusters are determined by various criteria like co-citation analysis. Clustering by textual similarity to organize the results of Web text search engines is described in Chang et al., xe2x80x9cCustomizable Multi-Engine Search Tool with Clustering,xe2x80x9d Proceedings of the Sixth International World-Wide Web Conference, pages 257-264, April, 1997. However, such implementations also fail to provide a user friendly user interface.
Examples of interfaces which have been developed for viewing information retrieval results include SenseMaker (See Baldonado et al., xe2x80x9cSenseMaker: An Information-Exploration Interface Supporting the Contextual Evolution of a User""s Interest,xe2x80x9d Proceedings of the ACM SIGCHI ""97 Conference on Human Factors in Computing Systems, pages 11-18, March, 1997) and Cat-a-Cone (See Hearst et al., xe2x80x9cCat-a-Cone: An Interactive Interface for Specifying Searches and Viewing Retrieval Results using a Large Category Hierarchy,xe2x80x9d Proceedings of the ACM SIGIR ""97 Conference on Research and Development in Information Retrieval, July, 1997). These articles, as well as those discussed above are hereby incorporated herein by reference.).
SenseMaker is an interface for information exploration across heterogeneous sources in a digital library. SenseMaker allows the user to interactively change the level of granularity and the organizational dimensions of a collection of documents that match the user""s interest. Cat-a-Cone is a 3D interface that allows a user to search and browse a large category hierarchy and the associated documents. The documents and the categories can be viewed concurrently. However, as with other systems, SenseMaker and Cat-a-Cone both focus on the text properties of documents and also present differing text organizational structures.
Other Web Image Search engines, such as Excalibur""s Image Surfer (http://isurf.yahoo.com) and Webseer (http://webseer.cs.uschicago.edu) show retrieved images in successive HTML pages. However, no technique for organizing the search results or query refinement is possible. Other popular text search engines, such as Alta Vista (http://www.altavista.digital.com) and Excite (http://www.excite.com) allow query refinement. Excite can group search results by Web sites. Moreover, both Excite and Alta Vista use co-occurrence analysis to show other relevant keywords for the query terms. While the technique is useful, there is no mechanism to find out the actual documents that correspond to the different keywords. The keywords are merely used to refine a search by including or excluding them. Allowing the user to see the actual documents/images that belong to a cluster would be more useful.
To overcome these and other difficulties, the present invention is directed to a method and apparatus for providing an interface for query refinement. The present invention provides to a user of a search engine a Query Result Visualization Environment (QRVE), a user interface which allows the user to refine the results of an original query by using variously clustered results of the original query. The results may be clustered using text, a primary object (or shape) or universal resource locator (URL). The members of the clusters may then be used to formulate the refined queries.